Field of the Invention
The present invention relates to a search system searching for a data word matching an input search key by a longest prefix match search, which is for example suitably used in a router of a packet-switched network.
Description of the Background Art
By a router provided in a network such as the Internet where a TCP/IP (Transmission Control Protocol/Internet Protocol) is used, forwarding, i.e. transferring a packet received from another host to another path, is performed. Each router stores a search table (a forwarding table) that defines the relation between an IP address and a path to a forwarding destination. The packet transfer path is determined in accordance with this search table. Specifically, a destination IP address included in the received packet is set as a search key and a next-hop IP address matching this search key is searched within the search table by a longest prefix match search.
In order to perform forwarding at a high speed, it is necessary to accelerate a search for the next-hop IP address within the search table. A content addressable memory (CAM) is often used as dedicated hardware for this purpose.
Japanese Patent Laying-Open No. 2006-5636 discloses an example in which a search table is configured using a TCAM (Ternary CAM). Specifically, the TCAM in this document includes a first CAM entry for setting higher-order bits of an IP address and a second CAM entry for setting lower-order bits of the IP address. The higher-order bits of the destination address of the received packet are compared with the first CAM entry, and then, the lower-order bits of the destination address of the received packet are compared with the second CAM entry.
Japanese Patent Laying-Open No. 2003-143198 discloses an example of a search table for which a TCAM is not used. Specifically, each bit of the transferred IP address is compared to a corresponding bit of an IP address defined within a forwarding table sequentially from the highest-order bit. Particularly, this document proposes a method of referring to the IP address by a plurality of bits in order to shorten the time required for forwarding.
According to the search method using a TCAM as disclosed in the above-mentioned Japanese Patent Laying-Open No. 2006-5636, the number of times of comparison between the search key and the search table can be decreased, but there is a disadvantage that power consumption is increased since a TCAM device is used. On the other hand, according to the search method not using a TCAM as disclosed in the above-mentioned Japanese Patent Laying-Open No. 2003-143198, comparison between the search key and the search table can be conducted with extremely little power consumption, but there is also a disadvantage that forwarding becomes time-consuming due to the increased number of times of search.